package com.company.greedy;

import java.util.HashMap;
import java.util.TreeSet;

/**
 * @author jrue
 * @description https://leetcode-cn.com/problems/candy/
 * 老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
 *
 * 你需要按照以下要求，帮助老师给这些孩子分发糖果：
 *
 * 每个孩子至少分配到 1 个糖果。
 * 相邻的孩子中，评分高的孩子必须获得更多的糖果。
 * 那么这样下来，老师至少需要准备多少颗糖果呢？
 *
 * 总是找到最小的一个设置为 -1
 *
 * @date 2019/11/14 13:51
 */
public class Candy {

    public static void main(String[] args) {
        System.out.println(candy(new int[]{1,2,2}));
    }

    public static int candy(int[] ratings) {
        if (ratings.length == 0) return 0;
        int[] dp = new int[ratings.length];
        dp[0] = 1;
        for (int i = 1; i < ratings.length; i++) {

            if (ratings[i] > ratings[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            } else if (ratings[i] < ratings[i -1 ]){
                dp[i] = Math.min(1,dp[i - 1] - 1);
                // 回溯
                if (dp[i] <= 0) {
                    dp[i] = 1;
                    for (int j = i; j>=1;j --) {
                        if (ratings[j] < ratings[j - 1] && dp[j] >= dp[j -1]) {
                            dp[j - 1]++;
                        }
                    }

                }
            } else {
                dp[i] = 1;
            }
        }

        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            res += dp[i];
        }

        return res;
    }
}
